package com.lwx.chapter7;

import java.util.ArrayList;
import java.util.List;

/**
 * 稀疏图 - 邻接表
 */
public class SparseGraph {
    //顶点数
    private int n;
    //边数
    private int m;
    /**
     * 是否为有向图
     */
    private boolean directed;
    /**
     * 任意两个顶点之间是否有边
     */
    List<List<Integer>> g;

    public SparseGraph(int n, Boolean directed) {
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List levelList = new ArrayList();
            g.add(levelList);
        }
    }
    int V() {
        return n;
    }

    int E() {
        return m;
    }

    /**
     * 在顶点v和顶点e之间建立一条边
     *
     * @param v
     * @param w
     */
    void addEdge(int v, int w) {
        //避免边数重复计数
        if(hasEdge(v,w)){
            return;
        }
        if (v < n && v >= 0 && w>=0 && w < n && v != w) {
            List<Integer> gLevelList = g.get(v);
            gLevelList.add(w);
            if (!directed) {
                List<Integer> wLevelList = g.get(w);
                wLevelList.add(v);
            }
            m++;
        }
    }

    Boolean hasEdge(int v, int w){
        if (v < n && v >= 0 && w>=0 && w < n) {
            List<Integer> gLevelList = g.get(v);
            for (int i = 0; i < gLevelList.size(); i++) {
                if(w == gLevelList.get(i)){
                    return true;
                }
            }
        }
        return false;
    }

    //使用迭代器来实现，返回指定节点的相连节点
    class  adjIterator{
        SparseGraph graph;
        int v;
        int index;
        public adjIterator( SparseGraph graph, int v){
            this.v = v;
            this.index = 0;
            this.graph = graph;
        }

        /**
         * v节点对应的第一个元素
         * @return
         */
        int begin(){
            index = 0;
            if(this.graph.g.get(v).size() > 0){
                return this.graph.g.get(v).get(index);
            }
            return -1;
        }

        /**
         *
         * @return
         */
        int next(){
            index ++;
            if(index < this.graph.g.size()){
                return this.graph.g.get(v).get(index);
            }
            return -1;
        }

        /**
         * v节点的是否遍历结束
         * @return
         */
        boolean end(){
            return index >= this.graph.g.get(v).size()-1;
        }
    }

}
